The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(#) → #
+(x, #) → x
+(#, x) → x
+(0(x), 0(y)) → 0(+(x, y))
+(0(x), 1(y)) → 1(+(x, y))
+(1(x), 0(y)) → 1(+(x, y))
+(1(x), 1(y)) → 0(+(+(x, y), 1(#)))
+(+(x, y), z) → +(x, +(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +(log'(x), 1(#)), #)
*(#, x) → #
*(0(x), y) → 0(*(x, y))
*(1(x), y) → +(0(*(x, y)), y)
*(*(x, y), z) → *(x, *(y, z))
*(x, +(y, z)) → +(*(x, y), *(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +(x, sum(l))
sum(app(l1, l2)) → +(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *(x, prod(l))
prod(app(l1, l2)) → *(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Rewrite Strategy: INNERMOST

(1) RenamingProof (EQUIVALENT transformation)

Renamed function symbols to avoid clashes with predefined symbol.

(2) Obligation:

Runtime Complexity Relative TRS:
The TRS R consists of the following rules:

0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

S is empty.
Rewrite Strategy: INNERMOST

(3) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)

Infered types.

(4) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

(5) OrderProof (LOWER BOUND(ID) transformation)

Heuristically decided to analyse the following defined symbols:
+', -, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
+' < log'
+' < *'
+' < sum
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(6) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
+', -, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
+' < log'
+' < *'
+' < sum
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(7) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

Induction Base:
+'(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0))

Induction Step:
+'(gen_#:1:true:false3_4(+(n6_4, 1)), gen_#:1:true:false3_4(+(n6_4, 1))) →_R^Ω(1)
0(+'(+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)), 1(#))) →_IH
0(+'(*5_4, 1(#)))

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(8) Complex Obligation (BEST)

(9) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
-, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(10) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)

Induction Base:
-(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

Induction Step:
-(gen_#:1:true:false3_4(+(n114310_4, 1)), gen_#:1:true:false3_4(+(n114310_4, 1))) →_R^Ω(1)
0(-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4))) →_IH
0(gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(11) Complex Obligation (BEST)

(12) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(13) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)

Induction Base:
eq(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
true

Induction Step:
eq(gen_#:1:true:false3_4(+(n117041_4, 1)), gen_#:1:true:false3_4(+(n117041_4, 1))) →_R^Ω(1)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) →_IH
true

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(14) Complex Obligation (BEST)

(15) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
ge < log'
*' < prod
app < inter
mem < inter

(16) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)

Induction Base:
ge(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
true

Induction Step:
ge(gen_#:1:true:false3_4(+(n150058_4, 1)), gen_#:1:true:false3_4(+(n150058_4, 1))) →_R^Ω(1)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) →_IH
true

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(17) Complex Obligation (BEST)

(18) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
*' < prod
app < inter
mem < inter

(19) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)

Induction Base:
log'(gen_#:1:true:false3_4(+(1, 0)))

Induction Step:
log'(gen_#:1:true:false3_4(+(1, +(n154183_4, 1)))) →_R^Ω(1)
+'(log'(gen_#:1:true:false3_4(+(1, n154183_4))), 1(#)) →_IH
+'(*5_4, 1(#))

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(20) Complex Obligation (BEST)

(21) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
*', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
*' < prod
app < inter
mem < inter

(22) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)

Induction Base:
*'(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

Induction Step:
*'(gen_#:1:true:false3_4(+(n250776_4, 1)), gen_#:1:true:false3_4(0)) →_R^Ω(1)
+'(0(*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0))), gen_#:1:true:false3_4(0)) →_IH
+'(0(gen_#:1:true:false3_4(0)), gen_#:1:true:false3_4(0)) →_R^Ω(1)
+'(#, gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(23) Complex Obligation (BEST)

(24) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
app < inter
mem < inter

(25) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
app(gen_nil:cons4_4(n266232_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n266232_4, b)), rt ∈ Ω(1 + n266232₄)

Induction Base:
app(gen_nil:cons4_4(0), gen_nil:cons4_4(b)) →_R^Ω(1)
gen_nil:cons4_4(b)

Induction Step:
app(gen_nil:cons4_4(+(n266232_4, 1)), gen_nil:cons4_4(b)) →_R^Ω(1)
cons(#, app(gen_nil:cons4_4(n266232_4), gen_nil:cons4_4(b))) →_IH
cons(#, gen_nil:cons4_4(+(b, c266233_4)))

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(26) Complex Obligation (BEST)

(27) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)
app(gen_nil:cons4_4(n266232_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n266232_4, b)), rt ∈ Ω(1 + n266232₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
sum, prod, mem, inter

They will be analysed ascendingly in the following order:
mem < inter

(28) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
sum(gen_nil:cons4_4(n268367_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n268367₄)

Induction Base:
sum(gen_nil:cons4_4(0)) →_R^Ω(1)
0(#) →_R^Ω(1)
#

Induction Step:
sum(gen_nil:cons4_4(+(n268367_4, 1))) →_R^Ω(1)
+'(#, sum(gen_nil:cons4_4(n268367_4))) →_IH
+'(#, gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(29) Complex Obligation (BEST)

(30) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)
app(gen_nil:cons4_4(n266232_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n266232_4, b)), rt ∈ Ω(1 + n266232₄)
sum(gen_nil:cons4_4(n268367_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n268367₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
prod, mem, inter

They will be analysed ascendingly in the following order:
mem < inter

(31) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
prod(gen_nil:cons4_4(n274993_4)) → *5_4, rt ∈ Ω(n274993₄)

Induction Base:
prod(gen_nil:cons4_4(0))

Induction Step:
prod(gen_nil:cons4_4(+(n274993_4, 1))) →_R^Ω(1)
*'(#, prod(gen_nil:cons4_4(n274993_4))) →_IH
*'(#, *5_4)

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(32) Complex Obligation (BEST)

(33) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)
app(gen_nil:cons4_4(n266232_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n266232_4, b)), rt ∈ Ω(1 + n266232₄)
sum(gen_nil:cons4_4(n268367_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n268367₄)
prod(gen_nil:cons4_4(n274993_4)) → *5_4, rt ∈ Ω(n274993₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
mem, inter

They will be analysed ascendingly in the following order:
mem < inter

(34) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n288435_4)) → *5_4, rt ∈ Ω(n288435₄)

Induction Base:
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(0))

Induction Step:
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(+(n288435_4, 1))) →_R^Ω(1)
if(eq(gen_#:1:true:false3_4(0), #), true, mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n288435_4))) →_L^Ω(1)
if(true, true, mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n288435_4))) →_IH
if(true, true, *5_4)

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(35) Complex Obligation (BEST)

(36) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)
app(gen_nil:cons4_4(n266232_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n266232_4, b)), rt ∈ Ω(1 + n266232₄)
sum(gen_nil:cons4_4(n268367_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n268367₄)
prod(gen_nil:cons4_4(n274993_4)) → *5_4, rt ∈ Ω(n274993₄)
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n288435_4)) → *5_4, rt ∈ Ω(n288435₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
inter

(37) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol inter.

(38) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)
app(gen_nil:cons4_4(n266232_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n266232_4, b)), rt ∈ Ω(1 + n266232₄)
sum(gen_nil:cons4_4(n268367_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n268367₄)
prod(gen_nil:cons4_4(n274993_4)) → *5_4, rt ∈ Ω(n274993₄)
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n288435_4)) → *5_4, rt ∈ Ω(n288435₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(39) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(40) BOUNDS(n^1, INF)

(41) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)
app(gen_nil:cons4_4(n266232_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n266232_4, b)), rt ∈ Ω(1 + n266232₄)
sum(gen_nil:cons4_4(n268367_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n268367₄)
prod(gen_nil:cons4_4(n274993_4)) → *5_4, rt ∈ Ω(n274993₄)
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n288435_4)) → *5_4, rt ∈ Ω(n288435₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(42) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(43) BOUNDS(n^1, INF)

(44) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)
app(gen_nil:cons4_4(n266232_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n266232_4, b)), rt ∈ Ω(1 + n266232₄)
sum(gen_nil:cons4_4(n268367_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n268367₄)
prod(gen_nil:cons4_4(n274993_4)) → *5_4, rt ∈ Ω(n274993₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(45) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(46) BOUNDS(n^1, INF)

(47) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)
app(gen_nil:cons4_4(n266232_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n266232_4, b)), rt ∈ Ω(1 + n266232₄)
sum(gen_nil:cons4_4(n268367_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n268367₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(48) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(49) BOUNDS(n^1, INF)

(50) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)
app(gen_nil:cons4_4(n266232_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n266232_4, b)), rt ∈ Ω(1 + n266232₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(51) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(52) BOUNDS(n^1, INF)

(53) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)
*'(gen_#:1:true:false3_4(n250776_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n250776₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(54) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(55) BOUNDS(n^1, INF)

(56) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)
log'(gen_#:1:true:false3_4(+(1, n154183_4))) → *5_4, rt ∈ Ω(n154183₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(57) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(58) BOUNDS(n^1, INF)

(59) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)
ge(gen_#:1:true:false3_4(n150058_4), gen_#:1:true:false3_4(n150058_4)) → true, rt ∈ Ω(1 + n150058₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(60) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(61) BOUNDS(n^1, INF)

(62) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)
eq(gen_#:1:true:false3_4(n117041_4), gen_#:1:true:false3_4(n117041_4)) → true, rt ∈ Ω(1 + n117041₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(63) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(64) BOUNDS(n^1, INF)

(65) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n114310_4), gen_#:1:true:false3_4(n114310_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n114310₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(66) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(67) BOUNDS(n^1, INF)

(68) Obligation:

Innermost TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(69) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(70) BOUNDS(n^1, INF)